//package acm.蓝桥19;
//
//import java.io.BufferedReader;
//import java.io.BufferedWriter;
//import java.io.InputStreamReader;
//import java.io.OutputStreamWriter;
//import java.io.PrintWriter;
//import java.io.StreamTokenizer;
//
///**
// * 满q叉树的节点数=q^0+q^1+...+q^n。一个满q叉树的节点数量=(q^h-1)/(q-1)。其中h是总高度 一个节点在树的第几层
// * s0~s1为第一层 (s1+1)~s2为第二层 s[k-1]+1~sk为第k层 1.计算总层数。 2.计算当前所在层 3.是否为最右孩子
// * 最左孩子=k+右侧个数+左侧的节点个数*q+1 最右孩子=k+右侧个数+左侧的节点个数*q+q
// */
//public class F_n叉树的节点 {
//	public static void main(String[] args) {
//		Reader sc = new Reader();
//		int t = sc.nextInt();
//		while (t-- > 0) {
//			int n = sc.nextInt();
//			int q = sc.nextInt();
//			int k = sc.nextInt();
//			Reader.pw.println(fun(n, q, k));
//		}
//		Reader.pw.flush();
//	}
//
//	public static long fun(int n, int q, int k) {
//		// 数的总高度
//		int pre=Math.log(k)
//		
//		// 此时的cur当前层到叶子节点层的数量。
//		long sn = 0;
//		long ln = 0;
//		long rn = 0;
//		long l = k;
//		long r = k;
//		cur++;
//		// 找到当前节点最下层的最左位置
//		while (r <= n) {
//			pre = sum;
//			sum += (long) Math.pow(q, cur - 1);
//			ln = l - pre - 1;
//			rn = sum - l;
//			l = l + rn + ln * q + 1;
//			r = k + rn + ln * q + q;
//			sn += r - l + 1;
//			cur++;
//		}
//		if(l<n) {
//			sn+=n-l;
//		}
//		return sn;
//	}
//
//	static class Reader {
//		static StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
//		static PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
//
//		public Reader(Object... o) {
//		}
//
//		public int nextInt() {
//			try {
//				in.nextToken();
//			} catch (Exception ignored) {
//			}
//			return (int) in.nval;
//		}
//	}
//}
